package com.zs.letcode.hash_table;

import java.util.Arrays;

/**
 * 只出现一次的数字
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * <p>
 * 说明：
 * <p>
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 * <p>
 * 示例 1:
 * <p>
 * 输入: [2,2,1]
 * 输出: 1
 * 示例2:
 * <p>
 * 输入: [4,1,2,1,2]
 * 输出: 4
 * 相关标签
 * 位运算
 * 数组
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/hash-table/xhsyr2/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/6/28 22:07
 */
public class Chapter4 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.singleNumber1(new int[]{4, 1, 2, 1, 2}));
    }

    private static class Solution {
        /**
         * 方法一：位运算
         *
         * @param nums
         * @return
         */
        public int singleNumber(int[] nums) {
            int num = 0;
            for (int i = 0; i < nums.length; i++) {
                num ^= nums[i];
            }
            return num;
        }

        public int singleNumber1(int[] nums) {
            Arrays.sort(nums);
            for (int i = 1; i < nums.length - 2; i++) {
                if (nums[i - 1] != nums[i] && nums[i] != nums[i + 1] && nums[i + 1] == nums[i + 2]) {
                    return nums[i];
                }
            }
            return nums[nums.length - 1];
        }
    }
}
